Recently, some techniques such as adding whiskers and attaching graphs to vertices of a given graph, have been proposed for constructing a new vertex decomposable graph. In this paper, we present a new method for constructing vertex decomposable graphs. Then we use this construction to generalize the result due to Cook and Nagel.

Let G be a finite simple graph on the vertex set V (G) and let S Í V (G). Adding a whisker to G at x means adding a new vertex y and edge xy to G where x Î V (G). The graph G È W (S) is obtained from G by adding a whisker to every vertex of S. We prove that if G \ S is either a graph with no chordless cycle of length other than 3 or 5, chordal graph or C5, then G È W (S) is a vertex decomposable graph.

Introduction: Vertex decomposability of a simplicial complex is a combinatorial topological concept which is related to the algebraic properties of the Stanley-Reisner ring of the simplicial complex. This notion was first defined by Provan and Billera in 1980 for k-decomposable pure complexes which is known as vertex decomposable when. Later Bjorner and Wachs extended this concept to non-pure complexes. Being defined in an inductive way, vertex decomposable simplicial complexes are considered as a well behaved class of complexes and has been studied in many research papers. Because of their interesting algebraic and topological properties, giving a characterization for this class of complexes is of great importance and is one of the main problems in combinatorial commutative algebra.....

Let Zn be the ring of integers modulo n. The unitary Cayley graph of Zn is defined as the graph G(Zn) with the vertex set Zn and two distinct vertices a,b are adjacent if and only if a 􀀀,b 2 U (Zn), where U (Zn) is the set of units of Zn. Let ℾ, (Zn) be the complement of G(Zn). In this paper, we determine the independence number of ℾ, (Zn). Also it is proved that ℾ, (Zn) is well-covered. Among other things, we provide condition under which ℾ, (Zn) is vertex decomposable.

We give upper bounds for the regularity of edge ideal of some classes of graphs in terms of invariants of graph. We introduce two numbers a’ (G) and n (G) depending on graph G and show that for a vertex decomposable graphG, reg (R/I (G)) £ min{a’ (G), n (G)} and for a shellable graph G, reg (R/I (G))£n (G). Moreover, it is shown that for a graphG, where Gc is a d-tree, we have pd (R/I (G)) =maxvÎV (G) {degG (v)}.

In this paper, we introduce a subclass of chordal graphs which contains d-trees and show that their complement are vertex decomposable and so is shellable and sequentially Cohen-Macaulay. This result improves the main result of Ferrarello who used a the-orem due to Froberg and extended a recent result of Dochtermann and Engstrom.

In this paper, we characterize the shellable complete t-partite graphs. It is also shown that for these types of graphs the concepts vertex decomposable, shellable and sequentially Cohen-Macaulay are equivalent. Furthermore, we give a combinatorial condition for the Cohen-Macaulay complete t-partite graphs.